package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func deepestLeavesSum(root *TreeNode) int {
	depthMap := map[*TreeNode]int{
		root: 0,
	}
	var sums []int
	que := []*TreeNode{root}
	for len(que) > 0 {
		head := que[0]
		que = que[1:]
		depth := depthMap[head]
		if len(sums) <= depth {
			sums = append(sums, head.Val)
		} else {
			sums[depth] += head.Val
		}
		if head.Left != nil {
			que = append(que, head.Left)
			depthMap[head.Left] = depth + 1
		}
		if head.Right != nil {
			que = append(que, head.Right)
			depthMap[head.Right] = depth + 1
		}
	}
	return sums[len(sums)-1]
}

func main() {
	n1 := &TreeNode{Val: 1}
	n2 := &TreeNode{Val: 2}
	n3 := &TreeNode{Val: 3}
	n4 := &TreeNode{Val: 4}
	n5 := &TreeNode{Val: 5}
	n6 := &TreeNode{Val: 6}
	n7 := &TreeNode{Val: 7}
	n8 := &TreeNode{Val: 8}
	n1.Left = n2
	n1.Right = n3
	n2.Left = n4
	n2.Right = n5
	n3.Right = n6
	n4.Left = n7
	n6.Right = n8
	println(deepestLeavesSum(n1))
}
